package com.tlvip.arithmetic.ch05;

/**
 * <p>description：使用数组实现的单向队列</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： </p>
 * Date 1/25/21</p>
 * Author mac
 *
 * @version 1.0
 */
public class MyArrayQueue<T> {
    int size;
    int head;
    int tail;
    QNode<T>[] qNodes;

    public MyArrayQueue(int size) {
        this.size = size;
        qNodes = new QNode[size];
    }

    public void push(QNode<T> qNode) {
        // 尾指针指向最后一位
        if (tail == size) {
            // 头尾指针碰撞时：队列中元素全部出队
            // 此时重置头尾指针，同时指向数组首位0下标即可
            if (head == tail) {
                head = tail = 0;
            } else {
                // 头尾指针不相等时，头指针下标大于0，则移动元素
                if (head == 0) {
                    return;
                }
                for (int i = 0; i <= size - head; i++) {
                    if (i == size - head) {
                        qNodes[i] = null;
                    } else {
                        qNodes[i] = qNodes[i + head];
                    }
                }
                tail = tail - head;
                head = head - head;
            }
        }
        qNodes[tail++] = qNode;
    }

    public QNode<T> pop() {
        if (tail > head) {
            QNode qNode = qNodes[head];
            qNodes[head] = null;
            ++head;
            return qNode;
        } else {
            return null;
        }
    }

    public boolean isEmpty() {
        return head == tail;
    }

    public static void main(String[] args) {
        int size = 3;
        // 初始化
        MyArrayQueue myArrayQueue = new MyArrayQueue(size);
        // 入队
        for (int i = 0; i < size; i++) {
            myArrayQueue.push(new QNode<>(i));
        }
        System.out.println(myArrayQueue.isEmpty());
        // 出队
        for (int i = 0; i < size; i++) {
            System.out.print(myArrayQueue.pop().value + "  ");
        }
        System.out.println();
        System.out.println(myArrayQueue.isEmpty());
        // 重置头尾指针到0下标
        for (int i = 3; i < 6; i++) {
            myArrayQueue.push(new QNode<>(i));
        }
        System.out.println(myArrayQueue.isEmpty());
        // 部分出队
        for (int i = 0; i < size - 1; i++) {
            System.out.print(myArrayQueue.pop().value + "  ");
        }
        System.out.println();
        for (int i = 9; i < 11; i++) {
            myArrayQueue.push(new QNode(i));
        }
        for (int i = 0; i < 3; i++) {
            System.out.print(myArrayQueue.pop().value + "  ");
        }
        System.out.println();
        System.out.println(myArrayQueue.isEmpty());
    }
}

class QNode<T> {
    T value;

    public QNode(T value) {
        this.value = value;
    }
}